翻訳と辞書 Words near each other ・ Park Battery ・ Park Beach ・ Park Bench Theories ・ Park Benches ・ Parity benchmark ・ Parity bit ・ Parity Committee for the Reconstruction of the Fourth International ・ Parity drive ・ Parity flag ・ Parity function ・ Parity game ・ Parity learning ・ Parity of a permutation ・ Parity of esteem ・ Parity of zero ・ Parity P ・ Parity plot ・ Parity price ・ Parity problem ・ Parity problem (sieve theory) ・ Parity product ・ Parity progression ratios ・ Parity-check matrix ・ Pariu cu viața ・ Pariu-ye Arab ・ Parium ・ Pariva Pranati ・ Parivaar (1987 film) ・ Parivach Zabandi Kayi ・ Parivar Vichora Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Parity P ： ウィキペディア英語版 Parity P In computational complexity theory, the complexity class ⊕P (pronounced "parity P") is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd. An example of a ⊕P problem is "does a given graph have an odd number of perfect matchings?" The class was defined by Papadimitriou and Zachos in 1983.〔C. H. Papadimitriou and S. Zachos. (Two remarks on the power of counting ). In ''Proceedings of the 6th GI Conference in Theoretical Computer Science'', ''Lecture Notes in Computer Science'', volume 145, Springer-Verlag, pp. 269-276. 1983.〕 ⊕P is a counting class, and can be seen as finding the least significant bit of the answer to the corresponding #P problem. The problem of finding the most significant bit is in PP. PP is believed to be a considerably harder class than ⊕P; for example, there is a relativized universe (see oracle machine) where P = ⊕P ≠ NP = PP = EXPTIME, as shown by Beigel, Buhrman, and Fortnow in 1998.〔R. Beigel, H. Buhrman, and L. Fortnow. NP might not be as easy as detecting unique solutions. In ''Proceedings of ACM STOC'98'', pp. 203-208. 1998.〕 Furthermore, PPP contains PH, whereas P⊕P is not known to even contain NP. ⊕P contains the graph isomorphism problem, and in fact this problem is low for ⊕P.〔.〕 It also trivially contains UP, since all problems in UP have either zero or one accepting paths. More generally, ⊕P is low for itself, meaning that such a machine gains no power from being able to solve any ⊕P problem instantly. The ⊕ symbol in the name of the class may be a reference to use of the symbol ⊕ in Boolean algebra to refer the exclusive disjunction operator. This makes sense because if we consider "accepts" to be 1 and "not accepts" to be 0, the result of the machine is the exclusive disjunction of the results of each computation path. == References == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Parity P」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.